package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.ListNode;

/**
 * 链表中倒数第k个节点
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9822.%20%E9%93%BE%E8%A1%A8%E4%B8%AD%E5%80%92%E6%95%B0%E7%AC%ACk%E4%B8%AA%E8%8A%82%E7%82%B9/README
 */
public class P22 {

    public static void main(String[] args) {

        ListNode<Integer> listNode5 = new ListNode<>(5, null);
        ListNode<Integer> listNode4 = new ListNode<>(4, listNode5);
        ListNode<Integer> listNode3 = new ListNode<>(3, listNode4);
        ListNode<Integer> listNode2 = new ListNode<>(2, listNode3);
        ListNode<Integer> listNode1 = new ListNode<>(1, listNode2);
        ListNode<Integer> head = new ListNode<>(0, listNode1);
        Solution solution = new P22().new Solution();
        ListNode<Integer> kthFromEnd = solution.getKthFromEnd(head, 3);
        ListNode.printLinkedList(kthFromEnd);

    }

    /**
     * 定义快慢指针 slow、fast，初始指向 head。
     *
     * fast 先向前走 k 步，接着 slow、fast 同时向前走，当 fast 指向 null 时，slow 指向的节点即为链表的倒数第 k 个节点。
     *
     */
    class Solution {
        public ListNode<Integer> getKthFromEnd(ListNode<Integer> head, int k) {
            ListNode<Integer> slow = head;
            ListNode<Integer> fast = head;
            while (k > 0) {
                fast = fast.next;
                k --;
            }
            while (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
}
